package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-09 21:38
 **/
public class LeetCode304 {
    //二维前缀和
    int[][] prefixSum;

    public LeetCode304(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        prefixSum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }


    //一维前缀和
    /*int m;
    int n;
    int[][] matix;
    int[] prefixSum;

    public LeetCode304(int[][] matrix) {
        this.matix = matrix;
        m = matrix.length;
        n = matrix[0].length;
        prefixSum = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cur = i * n + j;
                prefixSum[cur] = (cur > 0 ? prefixSum[cur - 1] : 0) + matix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; ++i) {
            int end = i * n + col2;
            int start = i * n + col1 - 1;
            //如果start越界直接为0
            sum += prefixSum[end] - (start < 0 ? 0 : prefixSum[start]);
        }
        return sum;
    }*/

    public static void main(String[] args) {
        LeetCode304 code = new LeetCode304(new int[][]{{3,0,1,4,2}, {5,6,3,2,1}, {1,2,0,1,5}, {4,1,0,1,7}, {1,0,3,0,5}});
        System.out.println(code.sumRegion(2, 1, 4, 3));
        System.out.println(code.sumRegion(1, 1, 2, 2));
        System.out.println(code.sumRegion(1, 2, 2, 4));
    }
}
